package com.example.demo.leetcode.top100;

import java.util.HashMap;
import java.util.Map;

/**
 * ******************************************************
 *
 * @author liugh9
 * @version 1.0
 * @classname _48路径总和III
 * @description
 * @date 2023/06/17 12:01
 * <p>
 * ******************************************************
 */
public class _48路径总和III {

    Map<Long, Integer> mem = new HashMap<Long, Integer>();//保存前缀树
    int target;

    public int pathSum(TreeNode root, int targetSum) {
        target = targetSum;
        //前缀树为0的个数至少是一个
        mem.put(0L, 1);

        return dfs(root, 0);
    }


    public int dfs(TreeNode root, long curSum) {
        if (root == null) return 0;
        //得到当前前缀树的值
        curSum += root.val;
        int res = 0;

        //得到我们想要前缀树的个数，想要前缀树值就是当前前缀树值减去目标值
        res += mem.getOrDefault(curSum - target, 0);

        //将当前前缀树的值保存
        mem.put(curSum, mem.getOrDefault(curSum, 0) + 1);

        // 进入下一层
        //遍历左边
        int left = dfs(root.left, curSum);
        //遍历右边
        int right = dfs(root.right, curSum);

        // 回到本层，恢复状态，去除当前节点的前缀和数量
        //防止左边前缀树影响右边前缀树，左边前缀树可能有个为6，右边正好想要一个前缀树为6的，这样子就出错了
        mem.put(curSum, mem.get(curSum) - 1);

        //结果是当前节点前缀树的个数加上左边满足的个数加右边满足的个数
        return res + left + right;
    }


    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
